\section{Introduction}
\label{sec:intro}

Consider a social network, e.g, the Facebook network. Lets say there
is a campaign that starts at some part of the network which we want to
spread to as many users as possible. We want the network topology to
facilitate this spread. This is a very common scenario, rnging from
advertisements for consumer products to campaign for political and
social causes. Perhaps more importantly, such flow of information via
social networks is crucial and tremendously useful in times of
emergencies like natural disasters, war and other calamities of large
magnitude.

Simply guaranteeing the connectivity of the network is far from
sufficient for this objective. For one, not all users of the network
may be interested in the campaign or the event, and thus may not pass
information. This is a huge problem due to the structure of social
networks where there are few users with very high degree forming
star-like structures. If a relatively small number of such users close
to the origin of the campaign or event decide not to participate in
the ongoing campaign, it is unlikely that the information will flow to
a large part of the network. Moreover, the effectiveness of a campaign
depends upon its influence on the users. A user is much more likely to
be influenced strongly by the campaign if the relevant information
reaches her through multiple of her friends as compared to when she
hears it from just one of her friends. 

Our objective in this work is two-fold. First, we want to understand
what kind of network toopology is favorable for this
objective. Second, armed with this understanding, we want to actively
drive the network topology towards this state by providing friends
suggestions.

\subsection{Problem Formulation}
Let $G$ be a graph with $n$ nodes and $m$ edges. Let $0< \alpha < 1$
be a parameter that governs the connectivity requirement. Let $p =
p(\alpha, G)$ be a function of $\alpha$ and $G$ that is the fraction
of nodes we can affod to be not interested in the campaign. We want to
ensure that if at most $pn$ nodes are deleted from the graph {\em
  adversarially}, there still exists a large connected component of
size at least $\alpha n$.

{\bf This, however, does not capture that each node should get the
  influence from multiple neighbors.}

Let $B$ be a specified budget: we are allowed to increase the degree
of each node by an additive amount $B$. This can be thought of as we
are making $B$ friends suggestion to each person. For simplicity, and
also because we are not concerned about studying if the friends
suggestions are accepted by the users, we will assum we can add $B$
neighbors for every node. 

Let us denote by $G'$ the graph obtained from $G$ after adding $B$
edges per node.  Note that $G$ and $G'$ have the same node set, and
$G$ is in fact a subgraph of $G'$.  The challenge is to select the
edges to add in such a way so that $p(\alpha, G')$ is as large as
possible for a specified value of $\alpha$. 

{\bf Does all this make sense? I am not very happy somehow ... }

